package bishi.likou_1_30;

/**
 * @auther Tang Xiaozun
 * @date 2022/1/30
 */
public class three {
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int left =0;int right =1;
        char[] chars = s.toCharArray();
        long qp = power;
        long hash = 0;
        hash+=chars[0];
        while (right<k&&right<chars.length){
            hash+=chars[right]*qp;
            hash%=modulo;
            qp*=power;
            right++;
        }
        if (hash==hashValue){
            return s.substring(left,right);
        }
        while(right<chars.length){
            hash+=chars[right]*qp;
            hash%=modulo;
            right++;
            if (hash==hashValue){
                return s.substring(left,right);
            }
            hash-=chars[left];
            left++;
        }
        return "";
    }
}
